package com.zh.note.huawei.onehundred.最大矩阵和or和最大子矩阵;

/**
 * @Author: zhanghuan
 * @date: 2023/9/4 10:56
 * @description: create it
 */

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        // Scanner scanner = new Scanner(System.in);
        // String[] split = scanner.nextLine().split(" ");
        // int rows = Integer.parseInt(split[0]);
        // int numCols = Integer.parseInt(split[1]);
        // int[][] inputMatrix = new int[rows][numCols];
        // for (int i = 0; i < rows; ++i) {
        //     String[] nums = scanner.nextLine().split(" ");
        //     for (int j = 0; j < nums.length; j++) {
        //         inputMatrix[i][j] = Integer.parseInt(nums[j]);
        //     }
        // }
        int rows = 3;
        int cols = 4;
        int[][] inputMatrix = {
                {-3, 5, -1, 5},
                {2, 4, -2, 4},
                {-1, 3, -1, 3}};

        int maxSum = solveMethod(cols, rows, inputMatrix);
        System.out.println(maxSum);
        // scanner.close();
    }

    private static int solveMethod(int cols, int rows, int[][] matrix) {
        int maxSum = 0;
        int[] colSum = new int[cols];
        for (int i = 0; i < rows; ++i) {
            Arrays.fill(colSum, 0);
            for (int j = i; j < rows; j++) {
                for (int k = 0; k < cols; k++) {
                    colSum[k] += matrix[j][k];
                }
                int maxColSum = maxSum(cols, colSum);
                if (maxColSum > maxSum) {
                    maxSum = maxColSum;
                }
            }
        }
        return maxSum;
    }

    private static int maxSum(int numCols, int[] a) {
        int maxSum = 0;
        int currentSum = 0;
        for (int i = 0; i < numCols; ++i) {
            currentSum += a[i];
            if (currentSum > maxSum) {
                maxSum = currentSum;
            }
            if (currentSum < 0) {
                currentSum = 0;
            }
        }
        return maxSum;
    }
}

